public class Solution {
    class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    /**
     * 求二叉树的深度
     * 思路：1.先去判断root为不为空，为空直接返回 0
     *      2.再去递归root的左树的高度，左树的高度用 leftTree接收
     *      3.再去递归root的右树的高度，右树的高度用 rightTree接收
     *      4.比较root左树和右树的高度
     *      5.返回左树和右树当中最大值 + 1的高度
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftTree = maxDepth(root.left);
        int rightTree = maxDepth(root.right);
        return leftTree > rightTree ? leftTree +1 : rightTree +1;

    }

    /**
     * 判断一棵树是否为平衡二叉树
     * 思路：1、首先去实现求树的高度的方法
     *      2、再去判断树的root为不为空
     *      3.然后利用求树的高度的算法，求左树和右树的高度
     *      4.左树和右树差值的绝对值不能超过2，否则为 false
     *      5.再去递归root的左树和root的右树判断是否为平衡二叉树
     * @param root
     * @return
     */
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        int leftH = maxDepth(root.left);
        int rightH = maxDepth(root.right);
        int margin = leftH - rightH;
        if (margin < 0) {
            margin = -margin;
        }
        return margin < 2 && isBalanced(root.left) && isBalanced(root.right);

    }

    /**
     * 判断两个数是否相同
     * 思路：1.先去判断 p和 q的root是否为空，如果为空返回true
     *      2.再去判断p和q当中是否有一个为空另一个不为空，如果是返回false
     *      3.然后判断p和q的val值相不相等，不相等返回false
     *      4、递归p的左树和q的左树判断两者是否相等 用leftTree接收
     *      5.递归p的右树和q的右树判断两者是否相等 用rightTree接收
     *      6.返回 leftTree && rightTree
     * @param p
     * @param q
     * @return
     */
    public boolean isSameTree (TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if ((p != null && q == null) || (p == null && q != null)) {
            return false;
        }
        if (p.val != q.val) {
            return false;
        }
        boolean leftTree = isSameTree(p.left,q.left);
        boolean rightTree = isSameTree(p.right,q.right);
        return leftTree && rightTree;
    }

    /**
     * 判断一颗树是否为另一颗树的子树
     * 思路：1、实现方法判断是否为相同树
     *      2、判断root和subRoot是否为空，为空返回true
     *      3.如果root和subRoot其中一个为空，另一个不为空返回false
     *      4.判断root和subRoot是否为相同树，相同返回true
     *      5.判断root的左子树和subRoot是否相同，相同返回true
     *      6.判断root的右子树和subRoot是否相同，相同返回true
     *      7.上面走完都不满足返回false
     * @param root
     * @param subRoot
     * @return
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null && subRoot == null) {
            return true;
        }
        if ((root != null && subRoot == null) || (root== null && subRoot != null)) {
            return false;
        }
        if(isSameTree(root,subRoot)) {
            return true;
        }
        if (isSubtree(root.left,subRoot)) {
            return true;
        }
        if (isSubtree(root.right,subRoot)) {
            return true;
        }
        return false;

    }
}
